package sort.leetcode;

/**
 * @author shkstart
 * 剑指offer51 求数组的逆序对个数
 * @create 2022-11-09-12:28
 */
public class Offer51 {
    public int reversePairs(int[] nums) {
        return reversePairsInternal(nums,0,nums.length-1);
    }

//    在nums的[l,r]区间中，求逆序对的个数
    private int reversePairsInternal(int[] nums, int l, int r) {

        if(l>=r){
            return 0;
        }
        //将数组不断拆分
        int mid = (r+l)>>1;
//        分别求出左右半区的逆序对个数
        int leftNum = reversePairsInternal(nums,l,mid);
        int rightNum = reversePairsInternal(nums,mid+1,r);

        if(nums[mid]>nums[mid+1]){
            //此时左半区间还有元素大于右半区间,需要merge操作
//  整个数组的逆序对数就是左半区间个数+右半区间的个数+merge的逆序对个数
            return leftNum+rightNum+merge(nums,l,mid,r);
        }else{
//            此时nums[mid]<=nums[mid+1]
//            整个数组有序，不需要merge
//            整个数组的逆序对数就是左半区间个数+右半区间的个数
            return leftNum+rightNum;
        }



    }

    private int merge(int[] nums, int l, int mid, int r) {

        int ret = 0;
        int[] temp = new int[r-l+1];
//        将元素组的元素拷贝到temp
        for(int i = l;i<=r;i++){
            temp[i-l] = nums[i];
        }
//        开始合并
        int i =l;
        int j = mid+1;
        for (int k = l; k <=r ; k++) {
            if(i>mid){
//                左半区处理完毕，将剩余的右半部接上
                nums[k] = temp[j-l];
                j++;
            }else if(j>r){
//                右半部分处理完毕
                nums[k]=temp[i-l];
                i++;
            }else if(temp[i-l]<=temp[j-l]){
//                左半部分< = 右半部分，整体有序，不构成逆序
                nums[k]=temp[i-l];
                i++;
            }else {
//                左半部分> 右半部分 构成逆序
                ret += (mid - i + 1);
                nums[k] = temp[j-l];
                j++;
            }

        }


        return ret;
    }
}
